プログラミング in OCaml 〜関数型プログラミングの基礎からGUI構築まで〜

2章

OCaml ではプログラムを構成する基本かつ中心的要素が式である

OCaml プログラムの実行とは，式を評価(evaluation)して， その値(value)を求めることである

OCaml では，プログラムを実行する前に型付けが行われ，悪い式は実行前に除外される

OCaml では，型付けに成功したプログラムは型エラーを起こさない

3章

比較演算子

=

<>

環境と静的有効範囲

プログラムの実行中には，実行している時点で定義さ れている(有効範囲にある)変数名とその値の組(これを束縛(binding)と呼ぶことがあり ます)の一覧表がメモリ上に保存されています。この一覧表のことを環境(environment) といいます。特に，プログラムの一番外側(プロンプトが出ている各時点)における環境 をトップレベル環境(top-level environment)，または大域環境(global environment)とい います。

3.3.2

code:ocaml

(* 3.1 *)

let dollar2yen d =

int_of_float (Float.round (d *. 114.32))

;;

let yen2dollar y =

(Float.round (float_of_int y /. 114.32 *. 100.)) /. 100.

;;

let dollar2yen_str d =

Printf.sprintf "%F dollars are %d yen." d (dollar2yen d)

;;

let capitalize s =

String.capitalize_ascii d

;;

(* 3.2 *)

if b1 then if b2 then true else false else false;;

if b1 then b1 = b2 else false;;

if b1 then true else if b2 then true else false;;

if b1 then true else b1 <> b2;;

(* 3.3 *)

not (not b1 || not b2);;

not (not b1 && not b2);;

tuple

要素はいくつでもよい

型が違ってもよい

パターンマッチ

tupleの要素を分割代入できる

code:ocaml

let pair = ("Hey", 123);;

val pair : string * int = ("Hey", 123)

let (word, age) = pair;;

val word : string = "Hey"

val age : int = 123

let (word, _) = pair;;

(* 同一の変数名は宣言不可 *)

let (a, a) = pair;;

Line 1, characters 8-9:

Error: Variable a is bound several times in this matching

ネストした要素も取り出せる

関数の仮引数など変数を宣言するところではどこでも使える

3.4.4

code:ocaml

(* 1 *)

let geo_mean (x, y) =

sqrt (x *. y)

;;

(* 2 *)

let bmi (name, height, weight) =

let b = weight /. (height *. height) in

let status = if b < 18.5 then "やせ" else

if b < 25. then "標準" else

if b < 30. then "肥満" else "高度肥満" in

Printf.sprintf "%sさんは%sです" name status

;;

(* 3 *)

let f (x, y) = (x + y, x - y);;

再帰

code:ocaml

(* 毎回計算していて非効率な例 *)

let rec fib n =

if n = 1 || n = 2 then 1 else fib(n - 1) + fib(n - 2);;

(* 計算結果をメモ化している *)

let fib n =

let rec fib_pair n =

if n = 1 then (1,0)

else

let (i,j) = fib_pair (n-1) in

(i+j, i)

in

let (i,_) = fib_pair n in

i;;

組み合わせ数

相互再帰

code:ocaml

let rec even n = (* n は正の整数 *)

if n = 0 then true else odd(n - 1)

and odd n =

if n = 0 then false else even(n - 1);;

末尾再帰

3.5.5

code:ocaml

(* 3.7 - 1 *)

let rec pow x n =

if n = 1 then x else x * (pow x (n-1));;

(* 3.7 - 2 *)

let rec pow_rs x n =

if n = 1 then x

else

if n mod 2 = 0 then

let t = pow_rs x (n/2) in t * t

else

x * (pow_rs x (n-1))

;;

(* 3.8 *)

let iterpow x n =

let rec iter (i, res) =

if i = n then res

else iter (i+1, res * x)

in

iter (1, x)

(* 3.10 *)

fib_pair <-- 4

fib_pair <-- 3

fib_pair <-- 2

fib_pair <-- 1

fib_pair --> (1, 0)

fib_pair --> (1, 1)

fib_pair --> (2, 1)

fib_pair --> (3, 2)

(* 3.11 - 1 *)

let rec gcd n m =

if n = 0 then m

else gcd (m mod n) n

(* 3.11 - 2 *)

let rec comb n m =

if n = m || m = 0 then 1

else (comb (n-1) m) + (comb (n-1) (m-1))

(* 3.11 - 3 *)

let iterfib n =

let rec fib_pair i (prev, current) =

if i = n then current

else fib_pair (i+1) (current, prev+current)

in

fib_pair 1 (0, 1)

(* 3.11 - 4 *)

let max_ascii s =

let rec iter i l =

let first :: _ = iter (String.length s - 1) []

|> List.map Char.code

|> List.sort compare

|> List.rev in

first |> Char.chr

(* 3.12*)

let rec pos n =

(pos (n-1) -. 1.0 /. (float_of_int (4 * (n-1) + 3))) +. 1.0 /. (float_of_int (4 * n + 1))

3.9

高階関数

関数型プログラミング言語一般がそうであるようにOCamlでも高階関数を定義できる

匿名関数も定義できる

fun"式"

code:ocaml

let rec sum_of (f, n) =

if n = 0 then 0 else sum_of (f, n-1) + f n

val sum_of : (int -> int) * int -> int = <fun>

fun x -> x * x

let square x = x * x (* これまで見てきた関数定義は *)

let square = fun x -> x * x (* 匿名関数に名前をつけてlet束縛することの略記法 *)

カリー化

部分適用

code:ocaml

let multi x = (fun y -> x * y);;

val multi : int -> int -> int = <fun>

multi 4;;

- : int -> int = <fun>

multi 4 2;;

- : int = 8

(* これまで書いてきた関数と実は同じ. これも部分適用可能 *)

let multi x y = x * y;;

val multi : int -> int -> int = <fun>

multi 4;;

- : int -> int = <fun>

(* 関数適用式は左結合するのでカリー化関数が順に適用されていく *)

multi 4 2;;

(multi 4) 2;;

((multi 4) 2);;

前置・中置演算子

定義が可能

code:ocaml

let ( *^-^) x y = x * y;;

val ( *^-^ ) : int -> int -> int = <fun>

( *^-^) v |> (> );;

- : (int -> int) -> bool = <fun>

let ( *^-^) x = x * 3;;

val ( *^-^ ) : int -> int = <fun>

let hello = 42;;

( *^-^) v < hello;;

- : bool = true

4章 多相性と型推論

多相性 polymorphism

多相的型システム polymorphic type system

多相性を許す型システム

一般的には多相性を追求すると型推論が難しくなるが、OCamlは実用的なレベルで両方を実現している

パラメトリック多相

関数の型情報の一部をパラメータ化することによって発生する多相性をパラメトリック多相（parametric polymorphism）と呼びます。パラメトリック多相による多相的関数は，型スキームの型変数をどう具体化しようともその振舞いは同じであるという特徴があります。

関数が引数に関する情報の一部のみで計算を行うことを示す

型変数は関数自身が操作しない部分の抽象表現といえる

アドホック多相

多くの言語では，+ という一つの記号が整数同士もしくは実数同士の足し算どちらでも使えます。これも多相性の一種ですが，値の取りうる型が，型スキームによる統一的な表現ではなく，場当たり的に決まっているので，このような多相性はアドホック多相（ad-hoc polymorphism） と呼ばれます。アドホック多相の特徴に，同じ関数でも引数の型によって振舞いが異なったりする，ということがあります。例えば，整数の足し算と浮動小数の足し算は，同じ足し算でも数の表現方法の違いから内部ではまったく異なった計算方式が取られます。

let多相

多相的に使える変数はletを使って定義されたもののみ

すべての変数に多相性を許すと型推論がうまくできなくなる

完全性completeness

OCamlの型推論は完全性を持つ

型推論

型推論は最も一般的な型を常に推論する

推論された一般的な型を主要な型 principal type と呼ぶ

基本的には推論される型を宣言する必要はない

型注釈をあえてつけることでデバグで便利なこともある

数学の世界では古くから「計算とは何か」「計算の限界とは何か」が考えられてきた

計算概念のモデルがいくつか生まれた

チューリングマシン (Turingmachine)

ラムダ計算 (λ-calculus)、組合わせ論理 (combinatorylogic)

複雑な計算も関数抽象式と関数適用の組み合わせで表現できる

コンビネータのポイントは、明示的にパラメータを導入することなく単純な関数を組み合わせてより複雑な関数を構成できること

Iコンビネータ

最も単純なコンビネータ

恒等関数とも呼ばれる

Kコンビネータ

定数関数を構成する

code:ocaml

let k x y = x

val k : 'a -> 'b -> 'a = <fun>

Sコンビネータ

code:ocaml

let s x y z = x z (y z);;

val s : ('a -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'c = <fun>

OCaml で fun 式と関数適用の組合せ「のみ」で表現できる関数（fun x -> x，fun x y -> x (x y) など）は S と K を関数適用で組み合わせることですべて表現できることが知られています。例えば I コンビネータは S K K として表せます。

5章 再帰的多相的データ構造: リスト

すべての要素の型が同一でなければならない

tupleとの最大の違い

constructionから来ている

右結合

code:ocaml

let many = 5 :: nums;;

let more = 9 :: 5 :: nums;;

マッチング節

code:ocaml

fun x -> match exp0 with

pattern1 -> exp1

| pattern2 -> exp2

(* funとmatch節の組み合わせ構文. ↑と等価 *)

function

pattern1 -> exp1

| pattern2 -> exp2

リストに関する操作のほとんどは再帰的に定義できる

code:ocaml

let rec length = function

[] -> 0

| _ :: rest -> 1 + length rest;;

val length : 'a list -> int = <fun>

let rec append l1 l2 =

match l1 with

[] -> l2

| v :: l1' -> v :: (append l1' l2);;

val append : 'a list -> 'a list -> 'a list = <fun>

let rec map f = function

[] -> []

| x :: rest -> f x :: map f rest;;

val map : ('a -> 'b) -> 'a list -> 'b list = <fun>

畳み込み fold

リスト間の要素をどのように計算するかの関数さえ与えれば再帰ですべての要素を処理できる

これを畳み込みという

連想リストとassoc関数

pairのリストで辞書を表現することもできる

ソートアルゴリズム

7章 レコードとヴァリアント

レコード

連想配列的なもの

フィールド名が特定の型に結びつく

強力な型付けには役立つが誤って上書きしないよう要注意

ヴァリアント